package com.fr.kak.map;
//平衡二叉搜索树
public class AVL {

	int height(Node node){
		if (node == null){
			return 0;
		}
		return node.height;
	}
	Node llRotate(Node node){
		Node x = node.left;
		node.right = x.left;
		x.left = node;
		
		node.height = Math.max(height(node.left), height(node.right));
		x.height = Math.max(height(x.left), height(x.right));
		return x;
	}
	Node rrRotate(Node node){
		Node x = node.right;
		node.left = x.right;
		x.right = node;
		
		node.height = Math.max(height(node.left), height(node.right));
		x.height = Math.max(height(x.left), height(x.right));
		return x;
	}
	
	Node lrRotate(Node node){
		Node x = node.left;
		node.left = rrRotate(x);
		return llRotate(node);
	}
	
	Node rlRotate(Node node){
		Node x = node.right;
		node.right = llRotate(x);
		return rrRotate(node);
	}
	int getBalance(Node node){
		if (node == null){
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	Node insert(Node node, int key){
		if(node == null){
			return new Node(key);
		}
		if (key < node.key){
			insert(node.left, key);
		}else if(key > node.key){
			insert(node.right, key);
		}else{
			return node;
		}
		
		node.height = 1 + Math.max(height(node.left), height(node.right));
		
		int balance = getBalance(node);
		if(balance > 1 && key < node.left.key){
			return llRotate(node);
		}
		if(balance < -1 && key > node.right.key){
			return rrRotate(node);
		}
		if(balance > 1 && key > node.left.key){
			return lrRotate(node);
		}
		if(balance < -1 && key < node.right.key){
			return rlRotate(node);
		}
		return node;
	}
	
	Node deleteNode(Node node,int key){
		if(node == null){
			return node;
		}
		if(key < node.key){
			deleteNode(node.left, key);
		}else if(key == node.key){
			if(node.left == null || node.right == null){
				if(node.left != null){
					node = node.left;
				}
				if(node.right != null){
					node = node.right;
				}
				if(node.left == null & node.right == null){
					node = null;
				}
			}else{
				Node tmp = minValueNode(node.right);
				node.key = tmp.key;
				node.right = deleteNode(node.right, tmp.key);
			}
		}else{
			deleteNode(node.right, key);
		}
		
		if(node == null){
			return node;
		}
		node.height = 1+ Math.max(height(node.left), height(node.right));
		
		int balance = getBalance(node);
		if (balance > 1 && getBalance(node.left) >= 0){
			return llRotate(node);
		}
		if(balance > 1 && getBalance(node.left) < 0){
			return lrRotate(node);
		}
		if (balance < -1 && getBalance(node.right)<= 0){
			return rrRotate(node);
		}
		if (balance < -1 && getBalance(node.right) > 0){
			return rlRotate(node);
		}
		return node;
	}
	Node minValueNode(Node node){
		Node current = node;
		while(current.left != null){
			current = current.left;
		}
		return current;
	}
}


class Node{
	int key;
	Node left;
	Node right;
	int height;
	
	Node(int key){
		this.key = key;
		this.height = 1;
	}
}
